ANS-Based Index Compression

Abstract

Techniques for effectively representing the postings lists associated with inverted indexes have been studied for many years. Here we combine the recently developed "asymmetric numeral systems" (ANS) approach to entropy coding and a range of previous index compression methods, including VByte, Simple, and Packed. The ANS mechanism allows each of them to provide markedly improved compression effectiveness, at the cost of slower decoding rates. Using the 426 GiB Gov2 collection, we show that the combination of blocking and ANS-based entropy-coding against a set of 16 magnitudebased probability models yields compression effectiveness superior to most previous mechanisms, while still providing r..